package com.lg;


public class MaxGoldProfit {

    public static void main(String[] args) {
        /*
        表格（n是金矿数量，w是工人数量）：
             n/w    |  1	2   3   4    5   6   7   8   9  10
        ————————————+——————————————————————————————————————————
            400/5   |  0	0	0	0	400	400	400	400	400	400
            500/5   |  0	0	0	0	500	500	500	500	500	900
            200/3   |  0	0	200	200	500	500	500	700	700	900
            300/4   |  0	0	200	300	500	500	500	700	800	900
            350/3   |  0	0	350	350	500	550	650	850	850	900
         */
        int w = 10;
        int[] p = {5, 5, 3, 4, 3};
        int[] g = {400, 500, 200, 300, 350};
        System.out.println("最大利润：" + maxGoldProfits(w, p, g));
    }

    /**
     * 类似于背包问题
     *
     * 把金矿数量设为n，
     * 工人数量设为w，
     * 金矿的含金量设为数组g[ ]，
     * 金矿所需开采人数设为数组p[ ].
     *
     * 设F(n, w)为n个金矿、w个工人时的最大利润函数，那么状态转移方程式如下：
     *     1）金矿数为0或工人数为0的情况下利润恒等于0
     *        F(n,w) = 0 (n=0或w=0)
     *     2）当所剩工人不够挖掘当前金矿时，只有一种最优子结构
     *        F(n,w)= F(n-1,W) (n≥1, w<p[n-1])
     *     3）正常情况下，每个金矿对应2种最优子结构，即：挖或者不挖，不需要保存整个表格，无论金矿多少座，我们只保存1行的数据即可，在计算下一行时，要从右向左统计，把旧的数据一个一个替换掉
     *        F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n≥1, w≥p[n-1])
     *
     * 时间复杂度是O(n*w) 空间复杂度是O(n*w)
     *
     * @param w 工人数量
     * @param p 金矿开采所需的工人数量
     * @param g 金矿储量
     * @return 获得金矿最大利润
     */
    public static int maxGoldProfits(int w, int[] p, int[] g) {
        //创建表格
        int[][] resultTable = new int[g.length + 1][w + 1];
        //填充表格
        for (int i = 1; i <= g.length; i++) {
            for (int j = 1; j <= w; j++) {
                if (j < p[i - 1]) {
                    // 最大利润等于上一轮的最大利润，即不挖
                    resultTable[i][j] = resultTable[i - 1][j];
                } else {
                    // 如果挖的利润大于上一轮的利润，就挖；否则就不挖
                    resultTable[i][j] = Math.max(resultTable[i - 1][j], resultTable[i - 1][j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        //返回最后一格的值，即最大利润值
        return resultTable[g.length][w];
    }
}
